1. Field of the Invention
The present invention relates to a packet transfer device such as a cell multiplexing device and a cell buffer device in an ATM communication network. Since a cell switch can be formed by combining a plurality of cell multiplexing devices, the present invention is also applicable to a cell switch which has each output port in a configuration of a cell multiplexing device according to the present invention. The cell buffer device of the present invention is not necessarily limited to handling of cells and is applicable to a buffer device in general. The present invention is also not necessarily limited to an application to the ATM communication network and is applicable to a packet switching network as well.
2. Description of the Background Art
Currently, researches on an ATM (Asynchronous Transfer Mode) communication scheme are actively conducted by researchers of the communication technology throughout the world. In an ATM communication scheme, fixed length packets called cells are used to transmit and switch information. In an ATM communication scheme, a high speed cell switching can be realized by a cell switch provided by the hardware inside a switch node, so that it is possible to realize an information transfer performance per unit time much superior than those of the existing communication networks.
An ATM communication scheme can set up a plurality of logical connections (Virtual Connection: VC) in one physical transmission link by using a connection identifier information called VPI (Virtual Path Identifier) and VCI (Virtual Channel Identifier) to be provided in a header of a cell. At each switch node within the network, routes are set up in advance for each VC, and the switch node determines an output route for outputting the cell according the connection identifier VPI and VCI of the cell. VPI and VCI are uniquely assigned at each physical transmission link between the switch nodes, so that the switch node has a function of rewriting values of VPI and VCI of a passing cell.
Up to now, the VC for which the quality is guaranteed in the ATM network has been either a CBR (Constant Bit Rate) connection or a VBR (Variable Bit Rate) connection. The CBR connection is a VC for transmitting the traffic in which the cell transmission rate (that is, a number of transmission cells per unit time, which is also referred to as a cell rate or a bandwidth) is constant and known in advance. The VBR connection is a VC for transmitting the traffic in which the cell transmission rate is not constant but some traffic characteristics such as a maximum value (peak rate) and an average value (average rate) are known in advance.
Basically, in a case of multiplexing a plurality of VCs in one physical transmission link while maintaining a sufficient quality, it is sufficient for a sum of the peak rates of all the VCs to be not greater than the bandwidth of the physical transmission link. This scheme is called a peak rate allocation. It is possible for the peak rate allocation to realize a sufficiently high physical transmission link utilization efficiency in a case of dealing only with the CBR connections, but a physical transmission link utilization efficiency cannot be very high in a case of dealing with the VBR connections. For this reason, there are many studies on a technique for improving the physical transmission link utilization efficiency by using the statistical multiplexing effect according to the traffic characteristics known in advance while maintaining the quality.
However, the ATM communication between computers is characterized by the fact that the traffic characteristics such as an average rate cannot be predicted in advance, and the characteristic called burstiness which indicates a coexistence of some timing at which a large amount of cells are transmitted instantaneously and some other timing at which no cell is transmitted. Consequently, for the ATM communication between computers, it is difficult to improve the network utilization efficiency while maintaining the quality by using the techniques used for CBR and VBR.
More specifically, for data transferred between computers, when the peak rate allocation is utilized to guarantee the quality, the network utilization efficiency will be lowered considerably, whereas when the statistical multiplexing effect is utilized as in a case of VBR, a large amount of cells arrive simultaneously at some output port of the cell switch because of the burstiness of the traffic, and the cell loss due to the buffer overflow will be caused unless a sufficient buffer capacity is provided at the cell switch. In addition, when the cell loss is caused, a re-transmission in unit of a packet formed by a plurality of cells will be carried out, so that the effective throughput will be lowered.
For this reason, in recent years, a service class called ABR (Available Bit Rate) has been proposed and studied. In this ABR, the network utilization efficiency is improved while guaranteeing the cell transfer quality (especially a quality concerning cell loss) by applying a flow control between terminals and switch nodes. In the ABR connection, when the switch node is about to fall into the cell congestion state, the source terminals are controlled to suppress cell transmissions before the cell congestion occurs at the switch node. Here, the traffic control information to be given to terminals is mainly carried by a cell called RM (Resource Management) cell. This traffic control from the switch node to the source terminal in the ABR has an unignorable delay time, so that there is a need to implement a large capacity buffer at the cell switch so as not to discard cells until the traffic control begins to function effectively.
Apart from these CBR, VBR and ABR, there is a service class called UBR (Unspecified Bit Rate) which is a class of the so called best effort service in which a terminal is not required to declare the characteristics of traffic to be outputted in detail to the network, but instead the network does not guarantee the transfer quality at all.
As described above, data between computers have the burstiness, so that in order to realize a satisfactory level of the cell loss rate for the UBR connections, it is considered that the implementation of a large capacity cell buffer in the cell switch is necessary.
Fortunately, the transfer delay time and the transfer delay jitter required by the traffic between computers are often not so severe compared with those required for the CBR and VBR. By implementing a large capacity cell buffer in the cell switch, the delay time and the delay jitter for the cell transmission increase, but it is considered that there are many applications that can tolerate such an increase of the delay time and the delay jitter.
In particular, in a case of the ABR and UBR services, it is considered necessary to provide means for avoiding the congestion of the network. One known means for avoiding the congestion is the so called EFCI (Explicit Forward Congestion Indication). In the EFCI, a header of each cell has an EFCI bit as an indication of a congestion experienced by that cell, and a cell switch within the network marks the EFCI but according to the congestion state. As each terminal utilizes the information of the EFCI, it becomes possible to avoid the congestion.
Next, the conventional per-VC fair queueing in the cell multiplexing device and the cell switch will be described.
First, the per-VC fair queueing which is required as the robustness in the ABR service will be described.
The ABR service works as the source terminal controls the transmission of cells according to the traffic control information given from the network. If some terminal ignores (either by fault or intentionally) the traffic control information given from the network, it may be difficult to recover from the congestion of the network.
This problem can be resolved by carrying out the per-VC fair queueing at a cell multiplexing device or a cell switch, so as to realize the fair cell multiplexing scheduling among VCs and the fair buffer allocation among VCs. By carrying out the per-VC fair queueing, the interaction among VCs can be suppressed to the minimum, and even if there is a VC which ignores the traffic control information, only that VC would fall into the congestion and the influence of that VC to the other VCs can be suppressed.
In addition, the per-VC fair queueing is also required from the fairness of the UBR service.
FIG. 1 shows an example of an unfair bandwidth allocation in the UBR service. In this example, the network has four terminals A, B, C and D, and one file server FS, which are connected through cell switches (or cell multiplexing devices) X, Y and Z and links 1, 2, 3, 4, 5, 6 and 7.
Now, when each cell switch is to multiplex cells regardless of a number of VCs set up to its input links, each cell switch treats the input ports equally. For example, at the cell switch X, in a case of multiplexing cells from the links 2 and 3 into the link 1, the cell switch X treats both links equally, so that if the bandwidth of the link 1 is 1.0, the bandwidth of 0.5 would be given to each of the links 2 and 3.
By the similar consideration, the bandwidth eventually given to each terminal would have the largest value 0.5 for the terminal A and the smallest value 0.125 for the terminals C and D. This is far from the ideal in which all terminals should be making accesses to the file server FS equally.
In addition, when the network falls into the congestion, the network transmits the EFCI information so that each terminal makes its bandwidth smaller. At this point, if there are terminals which obeys the EFCI information faithfully and terminals which ignore the EFCI information within the network, there is a problem in that only the terminals which are faithful to the EFCI information would suppress the cell transmission, and the terminals which ignore the EFCI information would end up obtaining unfairly large bandwidth resources.
These problems are caused by the fact that the cell switch treats the input links equally by ignoring a number of VCs multiplexed in each link. When the cell switch carries out the per-VC fair queueing and distributes the bandwidth according to a number of VCs, it becomes possible for the terminals to make accesses to the file server fairly.
Next, the conventional cell multiplexing device for carrying out the priority control among classes will be described.
FIG. 2 shows a configuration of a conventional cell multiplexing device for carrying out the priority control among classes. This cell multiplexing device of FIG. 2 is for multiplexing cells entered from N pieces of input ports into one piece of output port.
In the output buffer 101, cells of each class are separated by a class separation unit 102, and stored in a cell storage unit (101-1, 101-2, or 101-3) for each class provided therein, and a cell selection unit 103 selectively outputs cells to the output port according to the priority level of each class.
In addition, a number of cells stored in each buffer storage unit of the output buffer 101 is compared with a threshold value to generate a respective backpressure signal.
Each input buffer 100 also has a cell storage unit (100-1, 100-2, or 100-3) for each class, and cells are transferred to the output buffer 101 according to the priority level of each class among the classes which are permitted to output cells according to the backpressure signals.
In this configuration, there is a need to provide a plurality of cell storage units class by class in the output buffer, so that there is a drawback in that the realization of the output buffer becomes difficult when a number of classes increases. In particular, it has been necessary for the input rate of the output buffer to be N times greater (where N is a number of input ports) than a rate at the input port, so that when a number of classes and a number of input ports are large, it has been difficult to realize the output buffer with such complicated functions.
When the configuration of FIG. 2 is considered as one output port portion of a cell switch, the same problem also exists for the the cell switch which has buffers for the input ports.
Next, the conventional cell multiplexing device will be described. Here, the problems associated with a cell multiplexing device having input buffers as shown in FIG. 3 will be described.
FIG. 3 shows a cell multiplexing device for multiplexing cells entered from N input ports into one output port.
The output buffer 111 temporarily stores cells from the input ports and outputs cells according to a rate of an output port.
A number of cells stored in the output buffer 111 is compared with a threshold value to generate a backpressure signal. The input buffer 101 has one queue in correspondence to the output port, and transfers cells to the output buffer 111 only when the output is permitted by the backpressure signal.
Such a cell multiplexing device treats the input buffers 110 equally regardless of a number of VCs set up, so that there has been problems concerning the robustness in the ABR service and the fairness in the UBR service.
When the configuration of FIG. 3 is considered as one output port portion of a cell switch, the same problem also exists for the the cell switch which has buffers for the input ports.
Next, the conventional per-VC fair queueing in the cell buffer device will be described.
FIG. 4 shows a configuration of FIFO for each VC which realizes the per-VC fair queueing.
FIG. 4 shows a case of a cell buffer device in which the connection identifier information of the cell entered from the input link is notified to a buffer pointer management unit 130, the cell is temporarily stored in a cell buffer 131 by obtaining a write pointer indicating a writing position of the cell given from the buffer pointer management unit 130, and the cell is read out from the cell buffer 131 according to a read pointer indicating a cell to be read out given from the buffer pointer management unit 130 and outputted to the output link. The buffer pointer management unit 130 manages a buffer pointer indicating a position of each stored cell on the cell buffer 131.
Here, the buffer pointer management unit 130 manages the buffer pointer for each VC by using a VC table. FIG. 4 shows a well known management scheme using the pointer chain.
When the cell is entered, a buffer pointer is taken out from a head of an idle chain as the write pointer, and attached to a tail of the chain for VC corresponding to the input cell. At a time of outputting cell, a VC storing the cell is selected fairly, and a buffer pointer at its head is taken out as a read pointer. As a method for selecting a VC fairly at a time of cell output, the round robin scheme is known.
In order to select a VC by the round robin scheme, it is necessary to carry out the sequential search through the VC table as to whether there is any cell stored in the buffer, starting from a VC next to a VC which was outputted previously. It may be necessary to carry out this search for as many as almost all VCs within one cell period, but there are cases in which a number of VCs to be set up is well over several thousands, so that it has been difficult to realize this scheme in practice.
Next, the conventional cell buffer device for carrying out the priority control will be described.
FIG. 17 shows an exemplary configuration of a conventional cell buffer device for carrying out the priority control.
This cell buffer device of FIG. 17 has a class-1 cell storage unit 500-1 for temporarily storing cells with a low priority concerning the delay and a class-2 cell storage unit 500-2 for temporarily storing cells with a high priority concerning the delay, and their outputs are multiplexed by a class multiplexing FIFO 510.
A class management unit 520 receives a number of cells Na in the class-2 cell storage unit 500-2, and a number of cells Nb in the class multiplexing FIFO 510 as inputs, and issues a transfer commands to either class-1 or class-2, so that only the cell storage unit 500 of a class which received the transfer command will transfer cells to the class multiplexing FIFO 510.
In order to improve the performance of the priority control in this cell buffer device of FIG. 17, it is necessary to keep a number of cells stored in the class multiplexing FIFO 510 small, but in order not to lower the throughput, it is necessary to command the transfer so that the class multiplexing FIFO 510 will not become empty as much as possible (that is, so as not to cause the underflow in the class multiplexing FIFO 510). In addition, when either one of the cell storage unit 500 is empty, if the transfer is commanded to the empty cell storage unit 500 (a case which will be referred to as a vain-command in the following description), there would be a possibility for causing the underflow, so that it is necessary to issue the transfer command with respect to the cell storage unit 500 in which a stored cell exists.
According to these policies, the condition by which the class management unit 520 issues the transfer command to the class-2 cell storage unit 500-2 can be given by:(Nb≦1) and (Na≧1),while the condition for the transfer command to the class-1 cell storage unit 500-1 can be given by: (Nb≦1) and (Na=0).
Now, consider a case in which the delay times exist for a transmission of a number of cells information from the cell storage unit 500 or the class multiplexing FIFO 510 to the class management unit 520, a transmission of the transfer command from the class management unit 520 to the cell storage unit 500, and a cell transfer from the cell storage unit 500 to the class multiplexing FIFO 520. In such a case, the following problems are encountered conventionally.
First, due to these delay times, it has been impossible for the class management unit 520 to accurately judge whether the underflow is going to be caused in the class multiplexing FIFO 510 or not. For this reason, conventionally, the condition for not causing the underflow has been given by the comparison of a number of cells within the class multiplexing FIFO with a threshold value which is set larger for the delay time part. As a result, the average queue length of the class multiplexing FIFO 510 has been made longer, and this in turn has been lowering the performance of the priority control.
Also, because of the delay of a transmission of the information from the high priority class-2 cell storage unit 500-2, it has been impossible to accurately judge whether the class-2 cell storage unit 500-2 becomes empty or not. For this reason, there have been a case of issuing the vain-command by judging an actually empty state erroneously as not empty, or a case in which the output of the low priority class-1 cells with priority over the high priority class-2 cells is commanded by judging an actually not empty state erroneously as empty. As a result, the problems of a lowering of the throughput of the cell buffer device or a lowering of the performance have been encountered conventionally.
Note that the similar problems can also arise in various cell buffer devices other than the cell buffer device for carrying out the priority control. Namely, in a cell buffer device in which a management unit commands the cell transfer among a plurality of buffers, when the delay times exist for a transmission of a buffer information to the management unit, a transmission of the transfer command from the management unit to the buffer, and a cell transmission among the buffers, the similar problems of a lowering of the throughput of the cell buffer device or a lowering of the performance have been encountered conventionally.
Firstly, as there is a need to provide a plurality of cell storage units class by class in the output buffer, the realization of the output buffer becomes difficult when a number of classes increases. In particular, it has been necessary for the input rate of the output buffer to be N times greater (where N is a number of input ports) than a rate at the input port, so that when a number of classes and a number of input ports are large, it has been difficult to realize the output buffer with such complicated functions.
Secondly, as the conventional cell multiplexing device treats the input buffers equally regardless of a number of VCs set up, there has been problems concerning the robustness in the ABR service and the fairness in the UBR service.
On the other hand, the conventional cell buffer device is associated with the following problems.
Namely, in order to select a VC by the round robin scheme, it is necessary to carry out the sequential search through the VC table as to whether there is any cell stored in the buffer, starting from a VC next to a VC which was outputted previously. It may be necessary to carry out this search for as many as almost all VCs within one cell period, but there are cases in which a number of VCs to be set up is well over several thousands, so that it has been difficult to realize this scheme in practice.
In this regard, recently, there is a proposition of an algorithm to resolve this problem, as disclosed in M. Shreedhar & G. Varghese: “Efficient Fair Queueing using Deficit Round Robin”, ACM SIGCOMM '95, pp. 231-242, August 1995. This algorithm called DRR proposed in this paper manages VCs storing cells by using a concept of an active list, so that the search through the VC table is not necessary at a time of cell output. Consequently, even when a number of VCs to be set up is increased, it is possible to realize the selection of a cell to be outputted at high speed for the purpose of the per-VC fair queueing.
However, this DRR algorithm has a drawback in that a number of packets in proportion to a value of weight set up to each VC will be outputted at once because the packets are stored in the VC by VC classification, so that the output traffic resulting from this DRR algorithm will be very bursty.
In addition, in a cell buffer device in which a management unit commands the cell transfer among a plurality of buffers, when the delay times exist for a transmission of a buffer information to the management unit, a transmission of the transfer command from the management unit to the buffer, and a cell transmission among the buffers, the problems of a lowering of the throughput of the cell buffer device or a lowering of the performance have been encountered conventionally.